High capacity data networks, such as those using high-speed asynchronous transfer mode (ATM) switches offer promise not only of high-speed data delivery, but also a variety of quality of service (QoS) guarantees. An important element of establishing paths interconnecting nodes in a such high-speed data networks is an efficient, reliable routing mechanism.
Recently, the ATM Forum has standardized on certain PNNI protocols. As defined, these protocols provide for signaling and routing protocols that permit connection setup and release with multiple QoS parameters between nodes. These protocols also provide for exchange of topology state information between nodes. See further, Traffic Management Specification, Version 4.0, ATM Forum af-tm-0056.000, April, 1996; and Private Network-Network Interface Specification Version 1.0 (PNNI 1.0), af-pnni-0055.000, March 1996.
Many implementations of the PNNI protocols have been proposed, with a variety of performance and QoS features. An important consideration in many networks, such as those using the PNNI protocols, is interconnecting desired nodes while employing a minimum of network resources. In particular, it is desired to interconnect nodes using the shortest interconnecting paths. Additionally, it has become ever more important--especially for many time-dependent applications (such as multimedia applications)--to seek to achieve low or minimum delay time for transmission between selected nodes. QoS criteria based on such reduced or minimum delay are therefore of great importance for critical applications, and provide important competitive differentiation for service providers.
There are many solutions for selecting the shortest path (or minimum defined cost) between selected nodes, even in a network having a large number of interconnected nodes. Prominent among these shortest path algorithms is the well-known Dijkstra algorithm. Solutions based on the Dijkstra and other algorithms may often be modified to permit the inclusion of certain conditions relating to various QoS criteria. Experience with Dijkstra algorithm solutions and corresponding coding implementations have proven reliable in many cases and have been adopted for real-time network implementations. It is desirable, therefore, to reuse existing code and maintain functional compatibility between delay-constrained solutions and existing shortest path implementations. As is well known in the art, however, network solutions of the shortest path problem subject to an additive delay condition is a so-called "NP hard" problem that proves intractable in real-time network contexts using current implementation technologies.